package com.tgy;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020-11-30 10:44
 *
 *  基数排序
 */
public class RadixSort {

    public static void sort(int[] array) {

        if (array == null || array.length <= 1) {

            return;
        }

        // 找最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {

            if (array[i] > max) {

                max = array[i];
            }
        }

        int base = 10;
        int[] counts = new int[10];
        int[] datas = new int[array.length];

        /**
         * 获取第n位使用 (n + 1) * 10 取模
         */
        while (base <= max * 10) {

            Arrays.fill(counts, 0);

            for (int i = 0; i < array.length; i++) {
                datas[i] = array[i];
            }

            for (int i : array) {

                counts[(i % base)/(base / 10)]++;
            }

            // 设置排序的位置
            for (int i = 1; i < 10; i++) {

                counts[i] += counts[i - 1];
            }

            /**
             * 从后往前插入，维持低位已经排序的顺序
             */
            for (int i = datas.length - 1; i >= 0; i--) {
                int index = (datas[i] % base) / (base / 10);
                array[--counts[index]] = datas[i];
            }

            base = base * 10;
        }

    }

}
